package test.list;

// 无头双向链表实现
public class LinkedList {
    private Node head = null;
    private Node tail = null;
    //获取头

    public Node getHead() {
        return head;
    }

    //头插法
    public void addFirst(int data){
        Node newNode = new Node(data);
        //链表为空和不为空两种情况
        if(this.head == null){
            this.head = newNode;
            this.tail = newNode;
        }else{
            newNode.next = this.head;
            this.head.prev = newNode;
        }
        this.head = newNode;
    }
    //尾插法
    public void addLast(int data){
        Node newNode = new Node(data);
        //链表为空和不为空两种情况
        if(this.head == null){
            this.head = newNode;

        }else{
            this.tail.next = newNode;
            newNode.prev = tail;
        }
        this.tail = newNode;
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        if(index < 0 || index > this.size()){
            return false;
        }
        Node newNode = new Node(data);
        //头插
        if(index == 0){
            this.addFirst(data);
            return true;
        }//尾插
        if(index == this.size()){
            this.addLast(data);
            return true;
        }
        //原来自己的解法：没用for循环，有两个遍历变量
//        Node cur1 = null;
//        Node cur2 = this.head;
//        int indexNum = 0;
//        while(cur2 != null){
//            //如果循环次数相等，此时cur2是该下标原节点
//            if(index == indexNum){
//                //新数据需要和原数据的前一节点建立联系
//                cur1.next = newNode;
//                newNode.prev = cur1;
//                //需要和原节点的后一节点建立联系
//                newNode.next = cur2;
//                cur2.prev = newNode;
//                return true;
//            }
//            cur1 = cur1.next;
//            cur2 = cur2.next;
//            indexNum++;
//        }
        //记录prev
        Node prev = head;
        for(int i = 0;i < index - 1;i++){
            prev = prev.next;
        }
        //记录next
        Node next = prev.next;
        //与前一节点建立连接
        prev.next = newNode;
        newNode.prev = prev;
        //与后一节点建立连接
        newNode.next = next;
        next.prev = newNode;
        return true;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        for(Node cur = head;cur != null;cur = cur.next){
            if(cur.value == key){
                return true;
            }
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        for(Node cur = head;cur != null;cur = cur.next){
            if(cur.value == key){
                if(cur.prev == null && cur.next == null){
                    head = null;
                    tail = null;
                    break;
                }else if(cur.prev == null){
                    cur.next.prev = null;
                    head = cur.next;
                    break;
                } else if(cur.next == null){
                    cur.prev.next = null;
                    tail = cur.prev;
                    break;
                }else{
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                    break;
                }
            }
        }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        for(Node cur = head;cur != null;cur = cur.next){
            if(cur.value == key){
                if(cur.prev == null && cur.next == null){
                    head = null;
                    tail = null;
                    break;
                } else if(cur.prev == null){
                    cur.next.prev = null;
                    head = cur.next;
                } else if(cur.next == null){
                    cur.prev.next = null;
                    tail = cur.prev;
                }else{
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
        }
    }
    //得到单链表的长度
    public int size(){
        Node cur = this.head;
        int size = 0;
        while(cur != null){
            size++;
            cur = cur.next;
        }
        return size;
    }
    //展示链表
    public void display(){
        if(head == null){
            return;
        }
        StringBuilder string = new StringBuilder("[");
        Node cur = this.head;
        while(cur != null){
            string.append(cur.value);
            if(cur.next != null){
                string.append(",");
            }
            cur = cur.next;
        }
        string.append("]");
        System.out.println(string.toString());
    }
    //清空链表
    public void clear(){
        this.head = null;
        this.tail = null;
    }
    //测试头插
    private static void test1(){
        System.out.println("测试头插");
        LinkedList list = new LinkedList();
        list.addFirst(1);
        list.display();
        list.addFirst(2);
        list.display();
        list.addFirst(3);
        list.display();
    }
    //测试尾插
    private static void test2(){
        System.out.println("测试尾插");
        LinkedList list = new LinkedList();
        list.addLast(1);
        list.display();
        list.addLast(2);
        list.display();
        list.addLast(3);
        list.display();
    }
    //测试指定位置插入
    private static void test3(){
        System.out.println("测试指定位置插入");
        LinkedList list = new LinkedList();
        boolean b1 = list.addIndex(0,1); //true
        System.out.println(b1);
        list.display();
        boolean b2 = list.addIndex(2,2); //false
        System.out.println(b2);
        list.display();
        boolean b3 = list.addIndex(1,2); //true
        System.out.println(b3);
        list.display(); //[1,2]
    }
    //测试查找
    private static void test4(){
        System.out.println("测试查找");
        LinkedList list = new LinkedList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.display();
        System.out.println(list.contains(3));
        System.out.println(list.contains(4));
    }
    //测试删除第一次出现
    private static void test5(){
        System.out.println("测试删除第一次出现");
        LinkedList list = new LinkedList();
        list.addLast(1);
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.display();
        list.remove(1);
        list.display();
    }
    //测试删除所有
    private static void test6(){
        System.out.println("测试删除所有");
        LinkedList list = new LinkedList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(3);
        list.addLast(3);
        list.display();
        list.removeAllKey(3);
        list.display();
    }
    //测试长度
    private static void test7(){
        System.out.println("测试长度");
        LinkedList list = new LinkedList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.display();
        System.out.println(list.size());
    }
    //测试展示
    private static void test8(){
        System.out.println("测试展示");
        LinkedList list = new LinkedList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.display();
    }
    //测试清空
    private static void test9(){
        System.out.println("测试清空");
        LinkedList list = new LinkedList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.display();
        System.out.println("已展示清空前链表");
        list.clear();
        list.display();
    }
    public static void main(String[] args){
        test1();
        test2();
        test3();
        test4();
        test5();
        test6();
        test7();
        test8();
        test9();
    }
}
